Autonomous or semi-autonomous robotic devices are increasingly used within consumer homes and commercial establishments. Such devices may include a robotic vacuum cleaner, lawn mower, mop, or other similar devices. To operate autonomously or to operate with minimal (or less than fully manual) input and/or external control within a working environment, mapping methods are implemented within robotic devices such that the robotic device may autonomously create a map of the working environment and subsequently use it for navigation. Several mapping methods for robotic devices have been proposed. For example, a method for solving Simultaneous Localization And Mapping (SLAM) uses Extended Kalman Filter (EKF) techniques (see, e.g., U.S. Patent App. No. 2007/0293985, U.S. Patent App. No. 2006/0027404 and U.S. Patent App. No. 2014/0350839) for the construction of maps. The map may be considered complete when only a partial map of the working environment is constructed or it may be continuously updated to construct greater and greater portions of the working environment. This mapping method, in some implementations, captures images of the working environment, each image containing large amounts of feature points, to both create and continuously update the map. The robot localizes itself by capturing images with large amounts of feature points and comparing them to registered featured data. With an EKF technique, the pose of the robotic device and the position of features within the map of the environment are estimated and stored in a complete state vector while uncertainties in the estimates are stored in an error covariance matrix. The main drawback of using an EKF approach is the computational power required to process a large number of features having large total state vector and covariance matrix. The computational delays may limit the speed of robot movement and task performance. Additionally, the data collected in creating and updating the map requires large amounts of memory. Another issue with EKF SLAM approach is data association due to the presence of similar features in the map whereby different data association hypotheses can result in multiple distinct maps. While several data association algorithms have been developed to solve this issue, they cannot be implemented in real-time with commercially reasonable amounts of computing resources. Another issue with EKF-based SLAM approach, is the performance of the SLAM often highly depends on the accuracy of measurement noise covariance matrices, both of which are typically required a priori. Incorrect knowledge of sensor statistics can lead to degradation in performance. Furthermore, this type of SLAM method employs sophisticated techniques, often requiring considerable costs for implementation. While the high cost may be acceptable in certain cases, for mass consumerism of robotic devices a more cost-effective mapping system is needed.
Other mapping methods have been suggested in prior art wherein sensor data may be used to create an environmental map, the sensor being any one of sonar, laser, image, and the like. For example, U.S. Pat. No. 5,896,488 describes a method to map the environment using ultrasonic sensors wherein the robotic device follows along the walls while measuring distance and tracking movement to map the perimeter of the environment, however this method prevents the robotic device from performing work away from the perimeters while simultaneously mapping. U.S. Pat. No. 8,996,292 describes the construction of a grid map using distance sensors capable of detecting reflected light wherein the robotic device must rotate 360-degrees to map the area. This method is limited as the robotic device must complete a 360-degree rotation to map the area before beginning any coverage. Furthermore, similar mapping methods are often broadly explained (see, e.g., U.S. Patent App. No. 2003/0030398, U.S. Patent App. No. 2003/0229421 and U.S. Pat. No. 6,667,592), with no details given on how the sensor data is used to create the environmental map, which on its own is nontrivial.
None of the preceding discussion should be taken as a disclaimer of any of the described techniques, as the present approach may be used in combination with these other techniques in some embodiments.